package linkedlist;

/**
 * #分治
 *
 * @description: <a href="https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj">23. 合并 K 个升序链表</a>
 * @author: zhaoyinglin
 * @date: 2024/3/5
 */
public class MergeKLists {

    public static void main(String[] args) {
        ListNode[] listNodes = new ListNode[3];
        listNodes[0] = ListNode.generateLinkedList(new int[] { 1, 4, 5 });
        listNodes[1] = ListNode.generateLinkedList(new int[] { 1, 3, 4 });
        listNodes[2] = ListNode.generateLinkedList(new int[] { 2, 6 });

        Solution solution = new Solution();
        ListNode mergeList = solution.mergeKLists(listNodes);

        System.out.println(ListNode.toLinkedListString(mergeList));
    }

    static class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return divideMerge(lists, 0, lists.length - 1);
        }

        private ListNode divideMerge(ListNode[] lists, int start, int end) {

            if (start == end) {
                return lists[start];
            }

            if (start > end) {
                return null;
            }

            int mid = (start + end) / 2;
            ListNode leftMerge = divideMerge(lists, start, mid);
            ListNode rightMerge = divideMerge(lists, mid + 1, end);
            return mergeTwoList(leftMerge, rightMerge);

        }

        private ListNode mergeTwoList(ListNode p1, ListNode p2) {

            if (p1 == null || p2 == null) {
                return p1 == null ? p2 : p1;
            }

            ListNode mergeList = new ListNode(-1);

            ListNode head = mergeList;

            while (p1 != null && p2 != null) {

                int min;

                if (p1.val < p2.val) {
                    min = p1.val;
                    p1 = p1.next;
                } else {
                    min = p2.val;
                    p2 = p2.next;
                }

                mergeList.next = new ListNode(min);
                mergeList = mergeList.next;
            }

            mergeList.next = p1 != null ? p1 : p2;

            return head.next;
        }

    }

}
